// Created by WXX on 2021/12/22 20:59
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：8 ms, 在所有 C++ 提交中击败了69.05%的用户
 * 内存消耗：18.8 MB, 在所有 C++ 提交中击败了70.24%的用户
 */
class Solution {
public:
    vector<int> addNegabinary(vector<int> &A, vector<int> &B) {
        reverse(A.begin(), A.end());
        reverse(B.begin(), B.end());

        vector<int> C;
        for (int i = 0, a = 0, b = 0, c = 0; i < A.size() || i < B.size() || a || b; i++) {
            if (a == 1 && b == 2) a = b = 0;
            c = b, b = a, a = 0;
            if (i < A.size()) c += A[i];
            if (i < B.size()) c += B[i];
            C.push_back(c & 1);
            c >>= 1;
            a += c, b += c;
        }

        while (C.size() > 1 && !C.back()) C.pop_back();
        reverse(C.begin(), C.end());

        return C;
    }
};

void OutputBasicArray1D(vector<int> nums) {
    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    vector<int> A = {1, 1, 1, 1, 1}, B = {1, 0, 1};
    OutputBasicArray1D(Solution().addNegabinary(A, B));  // [1, 0, 0, 0, 0]

    return 0;
}
